<!DOCTYPE html>
<html lang="en">

<head>
	<meta http-equiv="content-type" content="text/html; charset=utf-8">
	<meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
	
	<!-- title -->
	
	<title>
	
		LeetCode | 
	 
	对线面试官
	</title>
	
	<!-- keywords,description -->
	 
		<meta name="description" content="Java一线大厂面试" />
	

	<!-- favicon -->
	
	<link rel="shortcut icon" href="/luffy/favicon.ico">
	


	<!-- search -->
	<script>
		var searchEngine = "https://www.baidu.com/s?wd=";
		if(typeof searchEngine == "undefined" || searchEngine == null || searchEngine == ""){
			searchEngine = "https://www.google.com/search?q=";
		}
		var homeHost = "";
		if(typeof homeHost == "undefined" || homeHost == null || homeHost == ""){
			homeHost = window.location.host;
		}
	</script>


	
<link rel="stylesheet" href="/luffy/css/main.css">

	
<link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.min.css">

	
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/highlightjs/cdn-release@9.17.1/build/styles/darcula.min.css">

	
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">


	
<script src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>

	
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>

	
<script src="https://cdn.jsdelivr.net/gh/highlightjs/cdn-release@9.17.1/build/highlight.min.js"></script>

	
<script src="https://cdn.jsdelivr.net/npm/jquery-pjax@2.0.1/jquery.pjax.min.js"></script>

	
<script src="/luffy/js/main.js"></script>

	
		
<script src="https://cdn.jsdelivr.net/npm/leancloud-storage/dist/av-min.js"></script>

		
<script src="https://cdn.jsdelivr.net/npm/valine@1.3.10/dist/Valine.min.js"></script>

	
	
<meta name="generator" content="Hexo 5.4.0"></head>

<body>
	<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?3efe99c287df5a1d6f0d02d187e403c1";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>

<header id="header">
    <a id="title" target="_blank" rel="noopener" href="https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzU4NzA3MTc5Mg==&action=getalbum&album_id=1657204970858872832&scene=126#wechat_redirect" class="logo">对线面试官</a>

	<ul id="menu">
		
	

	

		<li class="menu-item">
			<a href="https://gitee.com/zhongfucheng/Java3y" class="menu-item-link" target="_blank">
				【戳这里】获取更多原创干货💪💪
			</a>
		</li>
		<li class="menu-item">
			<a href="https://gitee.com/zhongfucheng/Java3y" class="menu-item-link" target="_blank">
				<i class="fa fa-github fa-2x"></i>
			</a>
		</li>
	</ul>
</header>

	
<div id="sidebar">
	<button id="sidebar-toggle" class="toggle" ><i class="fa fa-arrow-right " aria-hidden="true"></i></button>
	
	<div id="site-toc">
		<input id="search-input" class="search-input" type="search" placeholder="按回车全站搜索">
		<div id="tree">
			

			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										01-Java基础
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/01-Java%E5%9F%BA%E7%A1%80/01.%20%E6%B3%A8%E8%A7%A3/">
										01. 注解
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/01-Java%E5%9F%BA%E7%A1%80/02.%20%E6%B3%9B%E5%9E%8B/">
										02. 泛型
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/01-Java%E5%9F%BA%E7%A1%80/03.%20JavaNIO/">
										03. JavaNIO
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/01-Java%E5%9F%BA%E7%A1%80/04.%20%E5%8F%8D%E5%B0%84%E5%92%8C%E5%8A%A8%E6%80%81%E4%BB%A3%E7%90%86/">
										04. 反射和动态代理
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										02-Java并发
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/01.%20%E5%A4%9A%E7%BA%BF%E7%A8%8B%E5%9F%BA%E7%A1%80/">
										01. 多线程基础
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/02.%20CAS/">
										02. CAS
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/03.%20synchronized/">
										03. synchronized
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/04.%20AQS%E5%92%8CReentrantLock/">
										04. AQS和ReentrantLock
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/05.%20%E7%BA%BF%E7%A8%8B%E6%B1%A0/">
										05. 线程池
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/06.%20ThreadLocal/">
										06. ThreadLocal
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/07.%20CountDownLatch%E5%92%8CCyclicBarrier/">
										07. CountDownLatch和CyclicBarrier
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/08.%20%E4%B8%BA%E4%BB%80%E4%B9%88%E9%9C%80%E8%A6%81Java%E5%86%85%E5%AD%98%E6%A8%A1%E5%9E%8B/">
										08. 为什么需要Java内存模型
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/02-Java%E5%B9%B6%E5%8F%91/09.%20%E6%B7%B1%E5%85%A5%E6%B5%85%E5%87%BAJava%E5%86%85%E5%AD%98%E6%A8%A1%E5%9E%8B/">
										09. 深入浅出Java内存模型
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										03-Java容器
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/03-Java%E5%AE%B9%E5%99%A8/01.%20List%E9%9B%86%E5%90%88/">
										01. List集合
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/03-Java%E5%AE%B9%E5%99%A8/02.%20Map%E9%9B%86%E5%90%88/">
										02. Map集合
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										04-Java虚拟机
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/01.%20Java%E7%BC%96%E8%AF%91%E5%88%B0%E6%89%A7%E8%A1%8C%E7%9A%84%E8%BF%87%E7%A8%8B/">
										01. Java编译到执行的过程
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/02.%20%E5%8F%8C%E4%BA%B2%E5%A7%94%E6%B4%BE%E6%9C%BA%E5%88%B6/">
										02. 双亲委派机制
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/03.%20JVM%E5%86%85%E5%AD%98%E7%BB%93%E6%9E%84/">
										03. JVM内存结构
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/04.%20%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6%E6%9C%BA%E5%88%B6/">
										04. 垃圾回收机制
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/05.%20CMS%E5%9E%83%E5%9C%BE%E6%94%B6%E9%9B%86%E5%99%A8/">
										05. CMS垃圾收集器
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/06.%20G1%E5%9E%83%E5%9C%BE%E6%94%B6%E9%9B%86%E5%99%A8/">
										06. G1垃圾收集器
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/24/04-Java%E8%99%9A%E6%8B%9F%E6%9C%BA/07.%20JVM%E8%B0%83%E4%BC%98/">
										07. JVM调优
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										05-Spring
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/05-Spring/01.%20SpringMVC/">
										01. SpringMVC
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/05-Spring/02.%20Spring%E5%9F%BA%E7%A1%80/">
										02. Spring基础
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/05-Spring/03.%20SpringBean%E7%94%9F%E5%91%BD%E5%91%A8%E6%9C%9F/">
										03. SpringBean生命周期
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										06-Redis
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/06-Redis/01.%20Redis%E5%9F%BA%E7%A1%80/">
										01. Redis基础
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/06-Redis/02.%20Redis%E6%8C%81%E4%B9%85%E5%8C%96/">
										02. Redis持久化
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/06-Redis/03.%20Redis%E4%B8%BB%E4%BB%8E%E6%9E%B6%E6%9E%84/">
										03. Redis主从架构
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/06-Redis/04.%20Redis%E5%88%86%E7%89%87%E9%9B%86%E7%BE%A4/">
										04. Redis分片集群
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										07-消息队列
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/07-%E6%B6%88%E6%81%AF%E9%98%9F%E5%88%97/01.%20Kafka%E5%9F%BA%E7%A1%80/">
										01. Kafka基础
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/07-%E6%B6%88%E6%81%AF%E9%98%9F%E5%88%97/02.%20%E4%BD%BF%E7%94%A8Kafka%E4%BC%9A%E8%80%83%E8%99%91%E4%BB%80%E4%B9%88%E9%97%AE%E9%A2%98/">
										02. 使用Kafka会考虑什么问题
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										08-MySQL
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/08-MySQL/01.%20MySQL%E7%B4%A2%E5%BC%95/">
										01. MySQL索引
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/08-MySQL/02.%20MySQL%E4%BA%8B%E5%8A%A1%E5%92%8C%E9%94%81%E6%9C%BA%E5%88%B6%E5%92%8CMVCC/">
										02. MySQL事务和锁机制和MVCC
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/19/08-MySQL/03.%20MySQL%E8%B0%83%E4%BC%98/">
										03. MySQL调优
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										09-项目场景类
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/09-%E9%A1%B9%E7%9B%AE%E5%9C%BA%E6%99%AF%E7%B1%BB/01.%20%E5%A6%82%E4%BD%95%E5%AE%9E%E7%8E%B0%E5%8E%BB%E9%87%8D%E5%92%8C%E5%B9%82%E7%AD%89/">
										01. 如何实现去重和幂等
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/09-%E9%A1%B9%E7%9B%AE%E5%9C%BA%E6%99%AF%E7%B1%BB/02.%20%E7%B3%BB%E7%BB%9F%E9%9C%80%E6%B1%82%E5%A4%9A%E5%8F%98%E5%A6%82%E4%BD%95%E8%AE%BE%E8%AE%A1/">
										02. 系统需求多变如何设计
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/20/09-%E9%A1%B9%E7%9B%AE%E5%9C%BA%E6%99%AF%E7%B1%BB/03.%20%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/">
										03. 设计模式
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										10-计算机网络
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/08/25/10-%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C/01.%20HTTP/">
										01. HTTP
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
							<ul>
								<li class="directory">
									<a href="#" class="directory">
										<i class="fa fa-plus-square-o"></i>
										11-算法
									</a>
									
							<ul>
								<li class="file">
									<a href="/luffy/2021/09/01/11-%E7%AE%97%E6%B3%95/01.%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">
										01. 排序算法
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file active">
									<a href="/luffy/2021/09/02/11-%E7%AE%97%E6%B3%95/02.%20LeetCode%20Easy/">
										02. LeetCode Easy
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
							<ul>
								<li class="file">
									<a href="/luffy/2021/09/02/11-%E7%AE%97%E6%B3%95/02.%20LeetCode%20Medium/">
										02. LeetCode Medium
									</a>
								</li>
								<div class="article-toc" style="display: none;"></div>
							</ul>
			
								</li>
								
							</ul>
			
		</div>
	</div>
</div>

	<!-- 引入正文 -->
	<div id="content">
		<h1 id="article-title">

	02. LeetCode Easy
</h1>
<div class="article-meta">
	
	<span>3y</span>
	<span>2021-09-02 11:12:13</span>
		<div id="article-categories">
    
		<span>Categories：</span>
            
    

    
		<span>Tags：</span>
            
    
		</div>

</div>

<div id="article-content">
	<h2 id="LeetCode-1"><a href="#LeetCode-1" class="headerlink" title="LeetCode 1"></a>LeetCode 1</h2><blockquote>
<p> <strong>问题</strong>：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/two-sum/">https://leetcode-cn.com/problems/two-sum/</a> </p>
<pre><code class="java">/**
 * 两数之和
 * 1. Map存储着val 对应的下标
 * 2. target - num[i] 在Map中有存储，则能算出结果
 */
public class LeetCode1 &#123;

    public int[] twoSum(int[] nums, int target) &#123;
        Map&lt;Integer, Integer&gt; memo = new HashMap&lt;&gt;();
        for (int i = 0; i &lt; nums.length; i++) &#123;
            int val = target - nums[i];
            if (memo.containsKey(val)) &#123;
                return new int[]&#123;i, memo.get(val)&#125;;
            &#125; else &#123;
                memo.put(nums[i], i);
            &#125;
        &#125;
        return new int[2];
    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-20"><a href="#LeetCode-20" class="headerlink" title="LeetCode 20"></a>LeetCode 20</h2><blockquote>
<p><strong>问题</strong>：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。</p>
<p>有效字符串需满足：</p>
<ul>
<li>左括号必须用相同类型的右括号闭合。</li>
<li>左括号必须以正确的顺序闭合。</li>
</ul>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/valid-parentheses/">https://leetcode-cn.com/problems/valid-parentheses/</a></p>
<pre><code class="java">/**
 * 有效括号
 * 1. 借助Stack 栈先进先出的特性，将左侧括号进入栈
 * 2. 当前character不是左侧括号时，则pop出来比对是否匹配
 * 3. 注意要判断边界问题（在pop前 memo的大小是否为0，在遍历后，meme的大小是否为0）
 */
public class LeetCode20 &#123;
    public boolean isValid(String s) &#123;

        LinkedList&lt;Character&gt; memo = new LinkedList&lt;&gt;();
        for (int i = 0; i &lt; s.length(); i++) &#123;

            if (s.charAt(i) == &#39;[&#39; || s.charAt(i) == &#39;&#123;&#39; || s.charAt(i) == &#39;(&#39;) &#123;
                memo.push(s.charAt(i));
            &#125; else &#123;
                if (memo.size() == 0) &#123;
                    return false;
                &#125;
                Character pop = memo.pop();
                Character c = null;
                if (pop.equals(&#39;(&#39;)) &#123;
                    c = &#39;)&#39;;
                &#125;
                if (pop.equals(&#39;&#123;&#39;)) &#123;
                    c = &#39;&#125;&#39;;
                &#125;
                if (pop.equals(&#39;[&#39;)) &#123;
                    c = &#39;]&#39;;
                &#125;
                if (!c.equals(s.charAt(i))) &#123;
                    return false;
                &#125;
            &#125;

        &#125;
        if (memo.size() != 0) &#123;
            return false;
        &#125;

        return true;
    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-21"><a href="#LeetCode-21" class="headerlink" title="LeetCode 21"></a>LeetCode 21</h2><blockquote>
<p><strong>问题</strong>：将两个升序链表合并为一个新的 <strong>升序</strong> 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 </p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/merge-two-sorted-lists/">https://leetcode-cn.com/problems/merge-two-sorted-lists/</a></p>
<pre><code class="java">
/**
 * 合并两个有序链表
 * 1. 关键在于 使用虚拟头节点
 * 2. 记得移动 cur指针
 */
public class LeetCode21 &#123;


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) &#123;
        if (l1 == null) &#123;
            return l2;
        &#125;
        if (l2 == null) &#123;
            return l1;
        &#125;
        if (l1 == null &amp;&amp; l2 == null) &#123;
            return null;
        &#125;

        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;

        while (l1 != null &amp;&amp; l2 != null) &#123;
            if (l1.val &lt; l2.val) &#123;
                cur.next = l1;
                l1 = l1.next;
            &#125; else &#123;
                cur.next = l2;
                l2 = l2.next;
            &#125;
            cur = cur.next;
        &#125;
        while (l1 != null) &#123;
            cur.next = l1;
            l1 = l1.next;
        &#125;
        while (l2 != null) &#123;
            cur.next = l2;
            l2 = l2.next;
        &#125;
        return dummyHead.next;
    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-53"><a href="#LeetCode-53" class="headerlink" title="LeetCode 53"></a>LeetCode 53</h2><blockquote>
<p><strong>问题</strong>：给定一个整数数组 <code>nums</code> ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-subarray/">https://leetcode-cn.com/problems/maximum-subarray/</a></p>
<pre><code class="java">/**

 最大子序和(贪心算法)
 
 res作为历史最佳解，
 sum作为当前最佳解，
 每一次遍历nums数组时，
 都去动态更新res和sum。
 
 动态更新的逻辑为： 如果sum为正数，在有res记录历史最佳值的条件下，可以有恃无恐地继续累加，创造新高；
 如果sum为负数，不管下一次遍历值是多少累加后都不会大于它，见风使舵果断取下一个遍历值为当前最佳解。
 每一轮遍历结束后，如果当前最佳解优于历史最佳解，就会升任历史最佳解。
 */
public class LeetCode53 &#123;

    public int maxSubArray(int[] nums) &#123;

        int res = nums[0];
        int sum = 0;
        for (int num : nums) &#123;
            if (sum &gt; 0) &#123;
                sum = sum + num;
            &#125; else &#123;
                sum = num;
            &#125;
            res = Math.max(res, sum);
        &#125;

        return res;
    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-70"><a href="#LeetCode-70" class="headerlink" title="LeetCode 70"></a>LeetCode 70</h2><blockquote>
<p><strong>问题</strong>：假设你正在爬楼梯。需要 <em>n</em> 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？</p>
<p><strong>注意：</strong>给定 <em>n</em> 是一个正整数。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/climbing-stairs/">https://leetcode-cn.com/problems/climbing-stairs/</a></p>
<pre><code class="java">/**
 * 爬楼梯
 * 斐波拉契数列问题（使用备忘录，处理过的步数直接返回）
 * 1. 当n=1和n=2时 直接添加至备忘录且返回
 * 2. 当n在备忘录曾经计算过时，直接返回
 * 3. 备忘录添加 n的步数 (n-1) + (n-2)
 * 4. 返回备忘录的n
 */
public class LeetCode70 &#123;

    Map&lt;Integer, Integer&gt; memo = new HashMap&lt;&gt;();

    public int climbStairs(int n) &#123;

        if (n &lt; 3) &#123;
            memo.put(n, n);
            return memo.get(n);
        &#125;
        if (memo.containsKey(n)) &#123;
            return memo.get(n);
        &#125;
        memo.put(n, climbStairs(n - 1) + climbStairs(n - 2));

        return memo.get(n);
    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-101"><a href="#LeetCode-101" class="headerlink" title="LeetCode 101"></a>LeetCode 101</h2><blockquote>
<p><strong>问题</strong>：给定一个二叉树，检查它是否是镜像对称的。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/symmetric-tree/">https://leetcode-cn.com/problems/symmetric-tree/</a></p>
<pre><code class="java">/**
 * 给定一个二叉树，检查它是否是镜像对称的。
 * &lt;p&gt;
 * 1. 假如左子树和右子书都为null(说明只有&quot;root&quot;节点 返回true)
 * 2. 左右子树的val 不相等， return false
 */
public class LeetCode101 &#123;

    public boolean isSymmetric(TreeNode root) &#123;

        if (root == null) &#123;
            return true;
        &#125;
        return check(root.left, root.right);
    &#125;

    private boolean check(TreeNode left, TreeNode right) &#123;

        if (left == null &amp;&amp; right == null) &#123;
            return true;
        &#125;
        if (left == null || right == null || left.val != right.val) &#123;
            return false;
        &#125;
        return check(left.left, right.right) &amp;&amp; check(left.right, right.left);

    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-104"><a href="#LeetCode-104" class="headerlink" title="LeetCode 104"></a>LeetCode 104</h2><blockquote>
<p><strong>问题</strong>：给定一个二叉树，找出其最大深度，二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。</p>
<p><strong>说明:</strong> 叶子节点是指没有子节点的节点。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/">https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/</a></p>
<pre><code class="java">/**
 * 二叉树的最大深度
 * 递归找出左边和右边最大的深度 +1 就好了
 */
public class LeetCode104 &#123;

    public int maxDepth(TreeNode root) &#123;
        if (root == null) &#123;
            return 0;
        &#125;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-136"><a href="#LeetCode-136" class="headerlink" title="LeetCode 136"></a>LeetCode 136</h2><blockquote>
<p><strong>问题</strong>：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。</p>
<p>说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/single-number/">https://leetcode-cn.com/problems/single-number/</a></p>
<pre><code class="java">/**
 *  只出现一次的数字 hashMap 简单解决
 *
 *  可以用异或运算符
 */
public class LeetCode136 &#123;
  
//    public int singleNumber(int[] nums) &#123;
//
//        HashMap&lt;Integer, Integer&gt; map = new HashMap();
//
//        for (int num : nums) &#123;
//            if (map.containsKey(num)) &#123;
//                map.put(num, map.get(num) + 1);
//            &#125; else &#123;
//                map.put(num, 1);
//            &#125;
//        &#125;
//
//        for (Map.Entry&lt;Integer, Integer&gt; entry : map.entrySet()) &#123;
//            if (entry.getValue() == 1) &#123;
//                return entry.getKey();
//            &#125;
//        &#125;
//
//        return 0;
//    &#125;

    public int singleNumber(int[] nums) &#123;

        int a = 0;
        for (int num : nums) &#123;
            a = num ^ a;
        &#125;
        return a;
    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-155"><a href="#LeetCode-155" class="headerlink" title="LeetCode 155"></a>LeetCode 155</h2><blockquote>
<p><strong>问题</strong>：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。</p>
<p>push(x) —— 将元素 x 推入栈中。<br>pop() —— 删除栈顶的元素。<br>top() —— 获取栈顶元素。<br>getMin() —— 检索栈中的最小元素。</p>
<p><strong>提示：</strong><code>pop</code>、<code>top</code> 和 <code>getMin</code> 操作总是在 <strong>非空栈</strong> 上调用。</p>
</blockquote>
<pre><code class="java">/**
 * 借助 minStack 完成
 *
 * 首先扔进去一个MaxIntegerVal，这样就不用判空了
 */
class MinStack &#123;

    LinkedList&lt;Integer&gt; stack = new LinkedList&lt;&gt;();

    LinkedList&lt;Integer&gt; minStack = new LinkedList&lt;&gt;();

    /**
     * initialize your data structure here.
     */
    public MinStack() &#123;
        minStack.push(Integer.MAX_VALUE);
    &#125;

    public void push(int x) &#123;
        stack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    &#125;

    public void pop() &#123;
        stack.pop();
        minStack.pop();
    &#125;

    public int top() &#123;
        return stack.peek();
    &#125;

    public int getMin() &#123;
        return minStack.peek();
    &#125;

    public static void main(String[] args) &#123;


        MinStack obj = new MinStack();
        obj.push(2);
        obj.pop();
        int param_3 = obj.top();
        int param_4 = obj.getMin();

    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-160"><a href="#LeetCode-160" class="headerlink" title="LeetCode 160"></a>LeetCode 160</h2><blockquote>
<p><strong>问题</strong>：给你两个单链表的头节点 <code>headA</code> 和 <code>headB</code> ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 <code>null</code> 。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/intersection-of-two-linked-lists/">https://leetcode-cn.com/problems/intersection-of-two-linked-lists/</a></p>
<pre><code class="java">/**
 * 编写一个程序，找到两个单链表相交的起始节点。
 * 1. 两个节点相等，那就是相交；用Map来存储即可
 */
public class LeetCode160 &#123;
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) &#123;

        HashMap&lt;ListNode, ListNode&gt; map = new HashMap&lt;&gt;();

        if (headA == null || headB == null) &#123;
            return null;
        &#125;

        while (headA != null) &#123;
            map.put(headA, headA);
            headA = headA.next;
        &#125;
        while (headB != null) &#123;
            if (map.get(headB) != null) &#123;
                return headB;
            &#125;
            headB = headB.next;
        &#125;

        return null;
    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-169"><a href="#LeetCode-169" class="headerlink" title="LeetCode 169"></a>LeetCode 169</h2><blockquote>
<p><strong>问题</strong>：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/majority-element/">https://leetcode-cn.com/problems/majority-element/</a></p>
<pre><code class="java">
/**
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 1. Map大法好，遍历直接存储出现的次数，找到最大的即可
 * 2. 使用单个变量来记录，剩下的一定是&quot;多数&quot;的元素
 *   （从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个）
 */
public class LeetCode169 &#123;
    public int majorityElement(int[] nums) &#123;
        HashMap&lt;Integer, Integer&gt; keyVal = new HashMap&lt;&gt;();
        for (int num : nums) &#123;
            if (keyVal.containsKey(num)) &#123;
                keyVal.put(num, keyVal.get(num) + 1);
            &#125; else &#123;
                keyVal.put(num, 1);
            &#125;
        &#125;
        int max = Integer.MIN_VALUE;
        int key = 0;
        for (Map.Entry&lt;Integer, Integer&gt; entry : keyVal.entrySet()) &#123;
            if (entry.getValue() &gt; max) &#123;
                max = entry.getValue();
                key = entry.getKey();
            &#125;
        &#125;
        return key;
    &#125;


//    public int majorityElement(int[] nums) &#123;
//        int cand_num = nums[0];
//        int count = 1;
//        for (int i = 1; i &lt; nums.length; ++i) &#123;
//            if (cand_num == nums[i])&#123;
//                ++count;
//            &#125; else if (--count == 0) &#123;
//                cand_num = nums[i];
//                count = 1;
//            &#125;
//        &#125;
//        return cand_num;
//    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-206"><a href="#LeetCode-206" class="headerlink" title="LeetCode 206"></a>LeetCode 206</h2><blockquote>
<p><strong>问题</strong>：给你单链表的头节点 <code>head</code> ，请你反转链表，并返回反转后的链表。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/reverse-linked-list/">https://leetcode-cn.com/problems/reverse-linked-list/</a></p>
<pre><code class="java">/**
 * 反转链表
 * 1. 头节点指向 NULL
 * 2. 头结点和下一个节点不断往后移
 */
public class LeetCode206 &#123;
    public ListNode reverseList(ListNode head) &#123;
        ListNode cur = head;
        ListNode pre = null;

        while (cur != null) &#123;
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        &#125;
        return pre;
    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-226"><a href="#LeetCode-226" class="headerlink" title="LeetCode 226"></a>LeetCode 226</h2><blockquote>
<p><strong>问题</strong>：翻转一棵二叉树。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/invert-binary-tree/">https://leetcode-cn.com/problems/invert-binary-tree/</a></p>
<pre><code class="java">/**
 * 反转二叉树
 */
public class LeetCode226 &#123;
    public TreeNode invertTree(TreeNode root) &#123;
        if (root == null) &#123;
            return null;
        &#125;

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;
        return root;
    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-234"><a href="#LeetCode-234" class="headerlink" title="LeetCode 234"></a>LeetCode 234</h2><blockquote>
<p><strong>问题</strong>：给你一个单链表的头节点 <code>head</code> ，请你判断该链表是否为回文链表。如果是，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/palindrome-linked-list/">https://leetcode-cn.com/problems/palindrome-linked-list/</a></p>
<pre><code class="java">
/**
 * 请判断一个链表是否为回文链表。
 *
 * 借助栈结构，进栈出栈再判断一次
 */
public class LeetCode234 &#123;
    public boolean isPalindrome(ListNode head) &#123;
        if (head == null || head.next == null) &#123;
            return true;
        &#125;

        LinkedList&lt;ListNode&gt; stack = new LinkedList&lt;&gt;();

        ListNode cur = head;
        while (cur != null) &#123;
            stack.push(cur);
            cur = cur.next;
        &#125;

        while (!stack.isEmpty()) &#123;
            if (!Integer.valueOf(stack.pop().val).equals(Integer.valueOf(head.val))) &#123;
                return false;
            &#125;
            head = head.next;
        &#125;
        return true;
    &#125;

&#125;
</code></pre>
<h2 id="LeetCode-283"><a href="#LeetCode-283" class="headerlink" title="LeetCode 283"></a>LeetCode 283</h2><blockquote>
<p><strong>问题</strong>：给定一个数组 <code>nums</code>，编写一个函数将所有 <code>0</code> 移动到数组的末尾，同时保持非零元素的相对顺序。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/move-zeroes/">https://leetcode-cn.com/problems/move-zeroes/</a></p>
<pre><code class="java">/**
 * 283. 移动零
 * 遍历数据，只要不为0，则交换到index
 * 从index开始，复制为0
 */

public class LeetCode283 &#123;

    public void moveZeroes(int[] nums) &#123;
        int index = 0;
        for (int i = 0; i &lt; nums.length; i++) &#123;
            if (nums[i] != 0) &#123;
                nums[index] = nums[i];
                index++;
            &#125;
        &#125;
        for (int i = index; i &lt; nums.length; i++) &#123;
            nums[i] = 0;
        &#125;
    &#125;
&#125;
</code></pre>
<h2 id="LeetCode-448"><a href="#LeetCode-448" class="headerlink" title="LeetCode 448"></a>LeetCode 448</h2><blockquote>
<p><strong>问题</strong>：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。</p>
</blockquote>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/">https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/</a></p>
<pre><code class="java">
/**
 * 448. 找到所有数组中消失的数字
 * （不能用额外的空间）
 *
 * 数字范围1~n，而数组下标0~(n-1)，则可用数组原地标记数字是否出现过
 *
 *
 */
public class LeetCode448 &#123;
    public static List&lt;Integer&gt; findDisappearedNumbers(int... nums) &#123;
        List&lt;Integer&gt; res = new ArrayList&lt;&gt;();

     
        for (int i = 0; i &lt; nums.length; i++) &#123;
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] &gt; 0) &#123;
                nums[index] = -nums[index];
            &#125;
        &#125;

        for (int i = 0; i &lt; nums.length; i++) &#123;
            if (nums[i] &gt; 0) &#123;
                res.add(i + 1);
            &#125;
        &#125;

        return res;
    &#125;

&#125;
</code></pre>

</div>


    <div class="post-guide">
        <div class="item left">
            
              <a href="/luffy/2021/09/02/11-%E7%AE%97%E6%B3%95/02.%20LeetCode%20Medium/">
                  <i class="fa fa-angle-left" aria-hidden="true"></i>
                  02. LeetCode Medium
              </a>
            
        </div>
        <div class="item right">
            
              <a href="/luffy/2021/09/01/11-%E7%AE%97%E6%B3%95/01.%20%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">
                01. 排序算法
                <i class="fa fa-angle-right" aria-hidden="true"></i>
              </a>
            
        </div>
    </div>




<script>
	
	
</script>
	</div>
	<button id="totop-toggle" class="toggle"><i class="fa fa-angle-double-up" aria-hidden="true"></i></button>
</body>
</html>
